Solving 10385 - Duathlon (Ternary search)
[andmenj-acm.git] / 11590 - Prefix lookup / 11590.cpp
blobc335ecf2a2db5907ae6c50b87a75d070f4dfa5d2
1 //WA!
2 using namespace std;
3 #include <algorithm>
4 #include <iostream>
5 #include <iterator>
6 #include <sstream>
7 #include <fstream>
8 #include <cassert>
9 #include <climits>
10 #include <cstdlib>
11 #include <cstring>
12 #include <string>
13 #include <cstdio>
14 #include <vector>
15 #include <cmath>
16 #include <queue>
17 #include <deque>
18 #include <stack>
19 #include <list>
20 #include <map>
21 #include <set>
23 #define D(x) cout << #x " is " << (x) << endl
25 typedef unsigned long long Int;
26 const int BUFSIZE = 256;
27 char buf[BUFSIZE];
29 int M;
30 map<string, Int> ans;
32 struct node{
33 node * left, * right;
34 bool end; //is this node a complete prefix?
35 node(bool e) : end(e) {
36 left = right = NULL;
40 //not used, because I love to waste memory (It makes me feel dangerous)
41 void clean(node * n){
42 if (n == NULL) return;
43 clean(n->left); clean(n->right);
44 delete n;
47 Int f(string s, node * n){ //s = string built so far, n = the node we are standing at
48 Int left = 0, right = 0;
49 if (n->left != NULL){
50 left = f(s + "0", n->left);
52 if (n->right != NULL){
53 right = f(s + "1", n->right);
55 if (n->end){
56 Int x = ((1ULL) << (M - s.size())) - 1;
57 if (M - s.size() == 64){
58 x = ~(0ULL);
60 ans[s] = x - left + 1 - right;
62 Int ret = 0;
63 if (n->end){
64 ret = ans[s];
66 return ret + left + right;
69 int main(){
70 int n;
71 while (scanf("%d %d\n", &n, &M)==2 && !(n == 0 && M == 0)){
72 ans.clear();
73 node * root = new node(true);
74 while (n--){
75 fgets(buf, BUFSIZE, stdin);
76 node * cur = root;
77 for (int i=0; ; ++i){
78 if (buf[i] == '*'){
79 cur->end = true;
80 break;
82 if (buf[i] == '0'){
83 if (cur->left == NULL) cur->left = new node(false);
84 cur = cur->left;
85 }else if (buf[i] == '1'){
86 if (cur->right == NULL) cur->right = new node(false);
87 cur = cur->right;
92 f("", root);
94 int K;
95 scanf("%d\n", &K);
96 while (K--){
97 fgets(buf, BUFSIZE, stdin);
98 buf[strlen(buf)-2] = '\0'; //delete *\n
99 Int t = ans[string(buf)];
100 assert(t >= 0);
101 printf("%llu\n", t);
104 fgets(buf, BUFSIZE, stdin); //empty line
105 puts("");
107 return 0;